package str

import "strconv"

func restoreIpAddresses(s string) []string {
	bytelist := []byte(s)

	res := []string{}

	var backtrack func(bytelist []byte, track []string)
	backtrack = func(bytelist []byte, track []string) {
		// 停止条件
		if len(track) == 4 {
			if len(bytelist) == 0 {

				temp := ""
				for i := 0; i < 3; i++ {
					temp += track[i] + "."
				}
				temp += track[3]
				res = append(res, temp)
			}
			return
		}
		// 每一个间隔最大字符数为3
		for i := 0; i < len(bytelist) && i < 3; i++ {
			temp := string(bytelist[:i+1])
			if temp[0] == '0' && len(temp) > 1 {
				break
			}
			track = append(track, temp)
			num, _ := strconv.Atoi(temp)
			if num <= 255 {
				backtrack(bytelist[i+1:], track)
				track = track[:len(track)-1]
			}
		}

	}

	backtrack(bytelist, []string{})
	return res
}
